DROPS

Document

DOI: 10.4230/LIPIcs.SOCG.2015.522

Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited

Authors: Orit E. Raz, Micha Sharir, and Frank de Zeeuw

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

Let F in Complex[x,y,z] be a constant-degree polynomial, and let A,B,C be sets of complex numbers with |A|=|B|=|C|=n. We show that F vanishes on at most O(n^{11/6}) points of the Cartesian product A x B x C (where the constant of proportionality depends polynomially on the degree of F), unless F has a special group-related form. This improves a theorem of Elekes and Szabo [ES12], and generalizes a result of Raz, Sharir, and Solymosi [RSS14a]. The same statement holds over R. When A, B, C have different sizes, a similar statement holds, with a more involved bound replacing O(n^{11/6}). This result provides a unified tool for improving bounds in various Erdos-type problems in combinatorial geometry, and we discuss several applications of this kind.

Cite as

Orit E. Raz, Micha Sharir, and Frank de Zeeuw. Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 522-536, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{raz_et_al:LIPIcs.SOCG.2015.522,
  author =	{Raz, Orit E. and Sharir, Micha and de Zeeuw, Frank},
  title =	{{Polynomials Vanishing on Cartesian Products: The Elekes-Szab\'{o} Theorem Revisited}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{522--536},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.522},
  URN =		{urn:nbn:de:0030-drops-51031},
  doi =		{10.4230/LIPIcs.SOCG.2015.522},
  annote =	{Keywords: Combinatorial geometry, incidences, polynomials}
}

Document

DOI: 10.4230/LIPIcs.SOCG.2015.537

Bisector Energy and Few Distinct Distances

Authors: Ben Lund, Adam Sheffer, and Frank de Zeeuw

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

We introduce the bisector energy of an n-point set P in the real plane, defined as the number of quadruples (a,b,c,d) from P such that a and b determine the same perpendicular bisector as c and d. If no line or circle contains M(n) points of P, then we prove that the bisector energy is O(M(n)^{2/5}n^{12/5} + M(n)n^2). We also prove the lower bound M(n)n^2, which matches our upper bound when M(n) is large. We use our upper bound on the bisector energy to obtain two rather different results: (i) If P determines O(n / sqrt(log n)) distinct distances, then for any 0 < a < 1/4, either there exists a line or circle that contains n^a points of P, or there exist n^{8/5 - 12a/5} distinct lines that contain sqrt(log n) points of P. This result provides new information on a conjecture of Erdös regarding the structure of point sets with few distinct distances. (ii) If no line or circle contains M(n) points of P, then the number of distinct perpendicular bisectors determined by P is min{M(n)^{-2/5}n^{8/5}, M(n)^{-1}n^2}). This appears to be the first higher-dimensional example in a framework for studying the expansion properties of polynomials and rational functions over the real numbers, initiated by Elekes and Ronyai.

Cite as

Ben Lund, Adam Sheffer, and Frank de Zeeuw. Bisector Energy and Few Distinct Distances. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 537-552, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{lund_et_al:LIPIcs.SOCG.2015.537,
  author =	{Lund, Ben and Sheffer, Adam and de Zeeuw, Frank},
  title =	{{Bisector Energy and Few Distinct Distances}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{537--552},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.537},
  URN =		{urn:nbn:de:0030-drops-51086},
  doi =		{10.4230/LIPIcs.SOCG.2015.537},
  annote =	{Keywords: Combinatorial geometry, distinct distances, incidence geometry}
}

Search Results

Documents authored by de Zeeuw, Frank

Polynomials Vanishing on Cartesian Products: The Elekes-Szabó Theorem Revisited

Abstract

Cite as

Bisector Energy and Few Distinct Distances

Abstract

Cite as

Thanks for your feedback!

Could not send message